/**
 * describe:
 *
 * @author chaP
 * @date 2019/03/29
 */
package CodingTest.AC20190329;

import java.util.Stack;

/**
 * 题目描述
 给定一棵二叉搜索树，请找出其中的第k小的结点。例如， （5，3，7，2，4，6，8）    中，按结点数值大小顺序第三小结点的值为4。
 */
public class KthNode {
    class TreeNode{
        int val = 0;
        TreeNode left = null;
        TreeNode right = null;
        public TreeNode(int val){
            this.val = val;
        }
    }
    public int index = 0;
    //递归方法一：
    TreeNode KthNode1(TreeNode pRoot,int k){
        if(pRoot != null){
            TreeNode node =KthNode1(pRoot.left,k);
            if(node != null)
                return node;
            index ++;
            if(k == index)
                return pRoot;
            node = KthNode1(pRoot.right,k);
            if(node !=null)
                return node;
        }
        return null;
    }
    //递归方法二:
    private int i ;
    TreeNode KthNode2(TreeNode pRoot,int k){
        this.i = k;
        return helper(pRoot);
    }
    TreeNode helper(TreeNode pRoot){
        TreeNode temp = null;
        if(pRoot != null){
            if((temp = helper(pRoot.left))!=null) return temp;
            i--;
            if(i == 0) return pRoot;
            if((temp = helper(pRoot.right))!=null) return temp;
        }
        return null;
    }
    //非递归方法：
    TreeNode KthNode3(TreeNode pRoot,int k){
        Stack<TreeNode> s = new Stack<>();
        while(!s.isEmpty() || pRoot !=null){
            while(pRoot != null){
                s.push(pRoot);
                pRoot = pRoot.left;
            }
            if(!s.isEmpty()){
                pRoot = s.pop();
                k--;
                if(k == 0)
                    return pRoot;
                pRoot = pRoot.right;
            }

        }
        return null;
    }





}

